home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / prio / _k_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.0 KB  |  228 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _k_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/k_heap.h>
  17.  
  18.  
  19. #define KEY(i)   (HEAP[i]->key)
  20. #define INF(i)   (HEAP[i]->inf)
  21.  
  22.  
  23. k_heap::k_heap(int n, int k)  
  24. { if (n<=0) error_handler(1,string("k_heap constructor: illegal size = %d",n));
  25.   K = k;
  26.   HEAP = new k_heap_item[n+2];
  27.   for(int i = 0; i <= n; i++) HEAP[i] = nil;
  28.   count = 0; 
  29.   max_size = n;
  30. }
  31.  
  32. k_heap::k_heap(const k_heap& H)
  33. { K = H.K;
  34.   max_size = H.max_size;
  35.   count = H.count; 
  36.   HEAP = new k_heap_item[max_size+2];
  37.   for(int i = 1; i <= count; i++) 
  38.   { HEAP[i] = new k_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
  39.     H.copy_key(HEAP[i]->key);
  40.     H.copy_inf(HEAP[i]->inf);
  41.   }
  42. }
  43.  
  44. k_heap& k_heap::operator=(const k_heap& H)
  45. { clear();
  46.   delete HEAP;
  47.   K = H.K;
  48.   max_size = H.max_size;
  49.   count = H.count; 
  50.   HEAP = new k_heap_item[max_size+2];
  51.   for(int i = 1; i <= count; i++) 
  52.   { HEAP[i] = new k_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
  53.     copy_key(HEAP[i]->key);
  54.     copy_inf(HEAP[i]->inf);
  55.   }
  56.   return *this;
  57. }
  58.  
  59. k_heap::~k_heap()  
  60. { clear();
  61.   delete HEAP; 
  62. }
  63.  
  64. void k_heap::clear()
  65. { for(int i=1; i <= count; i++) 
  66.   { clear_key(KEY(i));
  67.     clear_inf(INF(i));
  68.     delete HEAP[i];
  69.    }
  70.   count = 0;
  71. }
  72.  
  73.  
  74. void k_heap::rise(int pos, k_heap_item it)
  75. { 
  76.   HEAP[0] = it;  // use "it" as stopper
  77.  
  78.   register int         pi = pos/K;        // parent index
  79.   register k_heap_item p  = HEAP[pi];     // parent node
  80.  
  81.  
  82.   if (int_type())
  83.      while(p->key > it->key)
  84.      { HEAP[pos] = p;
  85.        p->index = pos;
  86.        pos = pi;
  87.        pi /= K;
  88.        p = HEAP[pi];
  89.       }
  90.   else
  91.      while (cmp(p->key,it->key) > 0)
  92.      { HEAP[pos] = p;
  93.        p->index = pos;
  94.        pos = pi;
  95.        pi /= K;
  96.        p = HEAP[pi];
  97.       }
  98.  
  99.   HEAP[pos] = it;
  100.   it->index = pos;
  101. }
  102.  
  103.  
  104. void k_heap::sink(int pos, k_heap_item it)
  105. { 
  106.   register int ci = K*pos;    // child index
  107.   register k_heap_item p;     // child node
  108.  
  109.  
  110.   HEAP[count+1] = HEAP[count];   // stopper
  111.  
  112.   if (int_type())
  113.      while (ci <= count)
  114.      { 
  115.        p = HEAP[ci];
  116.  
  117.        int r = Min(count+1,ci+K);
  118.  
  119.        for (int j=ci+1;j<r;j++)
  120.            if (cmp(KEY(j),p->key)<0 ) 
  121.             { ci = j;
  122.               p = HEAP[j];
  123.              }
  124.  
  125.        if (it->key > p->key) 
  126.        { HEAP[pos] = p;
  127.          p->index = pos;
  128.          pos = ci;
  129.          ci *= K;
  130.         }
  131.        else  break;
  132.       }
  133.   else
  134.      while (ci <= count)
  135.      { 
  136.        p = HEAP[ci];
  137.  
  138.        int r = Min(count+1,ci+K);
  139.  
  140.        for (int j=ci+1;j<r;j++)
  141.            if (cmp(KEY(j),p->key)<0 ) 
  142.             { ci = j;
  143.               p = HEAP[j];
  144.              }
  145.        
  146.        if (cmp(it->key,p->key)>0) 
  147.        { HEAP[pos] = p;
  148.          p->index = pos;
  149.          pos = ci;
  150.          ci *= K;
  151.         }
  152.         else  break;
  153.       }
  154.  
  155.   HEAP[pos] =it;
  156.   it->index = pos;
  157. }
  158.  
  159.  
  160.  
  161.  
  162. void k_heap::decrease_key(k_heap_item it, GenPtr k)
  163. {
  164. //if (cmp(it->key,k)<0) error_handler(1,"k-heap:key too large in decrease_key");
  165.   clear_key(it->key);
  166.   copy_key(k);
  167.   it->key = k;
  168.   rise(it->index, it);
  169. }
  170.  
  171.  
  172.  
  173. k_heap_item k_heap::insert(GenPtr k, GenPtr i) 
  174. {
  175.   if (count == max_size) error_handler(1,"k_heap: overflow");
  176.   count++;
  177.   copy_key(k);
  178.   copy_inf(i);
  179.   k_heap_item it = new k_heap_elem(k,i,count);
  180.   rise(count,it);
  181.  
  182.   return it;
  183. }
  184.  
  185.  
  186.  
  187.  
  188. void k_heap::del_item(k_heap_item it)
  189. { k_heap_item p = HEAP[count];
  190.  
  191.   HEAP[count] = nil;
  192.  
  193.   count--;
  194.  
  195.   if (it != p)
  196.   { if (cmp(p->key,it->key) > 0)
  197.        sink(it->index, p);
  198.     else
  199.        rise(it->index, p);
  200.    }
  201.  
  202.   clear_key(it->key);
  203.   clear_inf(it->inf);
  204.  
  205.   delete it;
  206.  
  207.  
  208. }
  209.  
  210. void k_heap::change_inf(k_heap_item it, GenPtr i) 
  211. { clear_inf(it->inf);
  212.   copy_inf(i);
  213.   it->inf = i; 
  214.  }
  215.  
  216. void k_heap::print()
  217. { 
  218.   cout << "count = " << count << endl;
  219.   for(int i=1;i<=count;i++) 
  220.   { print_key(KEY(i));
  221.     //cout << "-";
  222.     //print_inf(INF(i));
  223.     cout << "  ";
  224.    }
  225.   newline;
  226. }
  227.  
  228.